#include <bits/stdc++.h>
#include <string>
using namespace std;

// n苹果数量  m盘子数量
int put_solution(int n, int m)
{
  if (n <= 0 || m == 1) // 如果苹果小于等于0或者盘子只有一个
    return 1;
  else
  {
    if (n < m) // 苹果数量比盘子少
      return put_solution(n, n);
    else  // 最后一个盘子一个苹果都不放  +  苹果减去盘子的数量 放 m个盘子里
      return put_solution(n, m - 1) + put_solution(n - m, m);
  }
}
int main()
{

  int k, n, m;
  cin >> k;
  while (k--)
  {
    cin >> n >> m;
    cout << put_solution(n, m) << endl;
  }
  return 0;
}